package offer.day16;

public class No24reverseList {
    /*
     * 面试题24：反转链表
     * 题目：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
     * 链表节点定义：
     * struct ListNode{
     * 	int m_nKey;
     * 	ListNode* m_pNext;
     * }
     *
     * 思路：从原链表头部开始转换链表的指向，需要使用三个指针。
     * 分别记录：第二个节点指向第一个节点，那么第二个在原链表时指向的那个将会丢失，所以用地三个指针记录此节点。
     * 并且要保证鲁棒性，完整性  考虑输入数据可能对程序的影响，避免系统崩溃
     * */
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode three = new ListNode(3);
        ListNode four = new ListNode(4);
        ListNode five = new ListNode(5);
        ListNode six = new ListNode(6);
        ListNode seven = new ListNode(7);
        head.next = second;
        second.next = three;
        three.next = four;
        four.next = five;
        five.next = six;
        six.next = seven;
        seven.next = null;
        showNode(head);
        ListNode reverseNode = reverseNode(head);
        showNode(reverseNode);
    }

    public static ListNode reverseNode(ListNode head){
        ListNode tmp=null;
        ListNode p=head;
        while(p!=null){
            ListNode next=p.next;
            p.next=tmp;
            tmp=p;
            p=next;
        }
        return tmp;
    }

    public static void showNode(ListNode head){
        ListNode tmp=head;
        while(tmp!=null){
            System.out.println(tmp);
            tmp=tmp.next;
        }
        System.out.println();
    }
}
